import java.util.Arrays;

public class EQueen {

  private static boolean show = true;

  private static int count;

  private static int n;

  private static int[] queen;

  private static boolean[] rk;

  private static boolean[] lk;

  private static int[] list;

  // 链表头。
  private static int ehead;

  /** *//**
   * @param n int
   */
  public static void go(int n) {
    EQueen.n = n;
    count = 0;
    queen = new int[n];
    rk = new boolean[2 * n - 1];
    lk = new boolean[2 * n - 1];
    list = new int[n];
    for (int i = 0; i < n; i++) {
      list[i] = i + 1;
    }
    list[n - 1] = -1;
    ehead = 0;
    long t1 = System.currentTimeMillis();
    step(0);
    long t2 = System.currentTimeMillis();
    System.out.println("count:" + count + " time:" + (t2 - t1));
    queen = null;
    rk = null;
    lk = null;
    n = count = 0;
  }

  private static void show() {
    System.out.println(Arrays.toString(queen));
  }

	static	int cc=0;
	static int cr=0;
  /** *//**
   * 
   * @param i int
   */
  private static void step(int i) {
	cr++;
    if (i == n) {
      count++;
      if (show) {
		System.out.println("in step "+i+" and cc is "+cc+"\n and cr is "+cr);
        show();
      }
      //System.exit(0);
    }

    int j = ehead;
    int previous = -1;
    while (j >= 0) {
	  cc++;
      if (!rk[i + j] && !lk[n - 1 + i - j]) {
        queen[i] = j;  //set queen i to value j

        if (previous >= 0) {
          list[previous] = list[j];
        }
        else {
          ehead = list[j];
        }
        rk[i + j] = true;
        lk[n - 1 + i - j] = true;	
		
        step(i + 1);

        if (previous >= 0) {
          list[j] = list[previous];
          list[previous] = j;
        }
        else {
          list[j] = ehead;
          ehead = j;
        }
        rk[i + j] = false;
        lk[i + n - 1 - j] = false;
      }
      previous = j;
      j = list[j];
    }
  }

  public static void main(String[] args) {
    int w = 8; // 14
    go(w);
  }
}
